package bfsAndDfs

// BFS
func findOrder(numCourses int, prerequisites [][]int) []int {
	var (
		// 邻接表
		edges = make([][]int, numCourses)
		// 入度表
		inDegree = make([]int, numCourses)
		// 存储入度为0的队列
		queue []int
		// 存储拓扑排序结果
		result []int
	)

	// 构造邻接表
	for _, info := range prerequisites {
		edges[info[1]] = append(edges[info[1]], info[0])
		inDegree[info[0]]++
	}

	// 将入度为0的元素存入队列
	for i, v := range inDegree {
		if v == 0 {
			queue = append(queue, i)
		}
	}

	// BFS，先从队列中取出节点node，然后遍历节点的所有邻接节点，将邻接节点入度-1，最后将入度为0的新节点压入队列中
	for len(queue) != 0 {
		e := queue[0]
		queue = queue[1:]
		result = append(result, e)
		for _, v := range edges[e] {
			inDegree[v]--
			if inDegree[v] == 0 {
				queue = append(queue, v)
			}
		}
	}
	if len(result) != numCourses {
		return []int{}
	}
	return result
}

// 基于DFS的拓扑排序
func findOrder1(numCourses int, prerequisites [][]int) []int {
	var (
		// 邻接表
		edges = make([][]int, numCourses)
		// 存储拓扑排序的结果队列
		result []int
		// 存储节点状态，0表示未搜索，1表示搜索中，2表示已搜索
		visited = make([]int, numCourses)
		// dfs函数(以node节点值作为传入参数)
		dfs func(node int)
		// 判断是否能完成拓扑排序
		valid = true
	)

	// 构建邻接表
	for _, info := range prerequisites {
		// info[1] -> info[0]
		edges[info[1]] = append(edges[info[1]], info[0])
	}

	// 1.更新当前节点状态为1（搜索中）
	// 2.
	dfs = func(node int) {
		// 搜索中
		visited[node] = 1
		// 遍历所有邻接节点
		for _, v := range edges[node] {
			// 搜索过程中遇到为1的节点，表示存在环
			if visited[v] == 0 {
				dfs(v)
				if !valid {
					return
				}
			} else if visited[v] == 1 {
				valid = false
				return
			}
		}
		// 搜索完成，压入栈中
		visited[node] = 2
		result = append(result, node)
	}

	// 遍历所有节点，只对未搜索的节点进行dfs
	for i := 0; i < numCourses; i++ {
		if visited[i] == 0 {
			dfs(i)
		}
	}

	if !valid {
		return []int{}
	}
	return reverse(result)
}

func reverse(nums []int) []int {
	n := len(nums)
	for i := 0; i < n/2; i++ {
		nums[i], nums[n-1-i] = nums[n-1-i], nums[i]
	}
	return nums
}
